package com.code.leetcode._202507;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//57 插入区间
public class Insert {
    /**
     * 给你一个无重叠的，按照区间起始端点排序的区间列表intervals，其中intervals[i]=[starti,endi]表示第i个区间的开始和结束，
     * 并且intervals按照starti升序排序。同样给定一个区间newintervals=[start,end]表示另外一个区间的开始和结束
     * 在intervals中插入区间newintervals，使得intervals依然按照starti升序排序，且区间之鉴不重叠(如果有右必要的话，可以合并区间)
     * 返回插入之后的intervals。
     * 注意，你不需要原地修改intervals，你可以创建一个新数组然后返回它。
     * 示例1:输入：intervals=[[1,3],[6,9]], newInterval = [2,5]
     * 输出：[[1,5],[6,9]]
     * 示例2：输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
     * 输出：[[1,2],[3,10],[12,16]]
     * 解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
     **/
    public static void main(String[] args) {
        Insert i = new Insert();
        System.out.println(Arrays.deepToString(i.insert(new int[][]{{1, 3}, {6, 9}}, new int[]{8, 10})));
    }

    /**
     * 对于区间s1=[l1,r1]和s2=[l2,r2]，如果他们之鉴没有重叠，说明要么s1在s2的左侧，此时右r1<l2;要么s1在s2的右侧，此时有l1>r2
     * 如果r1<l2和l1>r2二者均不满足，说明s1和s2必定有交集，他们的交集即为
     * [max(l1,l2),min(r1,r2)],并集即为[min(l1,l2),max(r1,r2)]
     * 模拟
     * 在给定的区间集合x互不重叠的前提下，当我们需要插入一个新的区间s=[left,right]时，我们只需要：
     * 1、找出所有与区间s重叠的区间集合x‘
     * 2、将x’中的所有区间连带上区间s合并成一个大区间
     * 3、最终的答案即为不为x‘重叠的区间以及合并后的大区间
     * 这样做的正确性在于，给定的区间集合中任意两个区间都是没有交集的，因此所有需要合并的区间，就是所有与区间s重叠的区间
     * 并且，在给定的区间集合已经按照左端点排序的前提下，所有与区间s重叠的区间在数组intervals中下标范围是连续的，因此我们可以对
     * 所有的区间进行一次遍历，就可以找到这个连续的小标范围。
     * 当我们遍历到区间[li,ri]时：
     * 1、如果ri<left,说明[li,ri]与s不重叠并且在其左侧，我们可以直接将[li,ri]加入答案
     * 2、如果li>right，说明[li,ri]与s不重叠并且在其右侧，我们可以直接将[li,ri]加入答案
     * 3、如果上面两种情况均不满足，说明[li,ri]与s重叠，我们无需将[li,ri]加入答案，此时，我们需要将s与[li,ri]合并，即将s更新
     * 为其与[li,ri]的并集。
     * 那么我们应当在什么时候将区间s加入答案呢？由于我们需要保证答案也是按照左端点排序的，因此当我们遇到第一个满足li>right的区间时，
     * 说明以后遍历到的区间不会与s重叠，并且它们左端点一定会大于s的左端点，此时我们就可以将s加入答案。特别的，如果不存在这样的区间
     * 我们需要在遍历结束后将s加入答案。
     **/
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int left = newInterval[0];
        int right = newInterval[1];
        boolean placed = false;
        List<int[]> ansList = new ArrayList<>();
        for (int[] interval : intervals) {
            if (interval[0] > right) {
                //在插入区间的右侧且无交集
                if (!placed) {
                    ansList.add(new int[]{left, right});
                    placed = true;
                }
                ansList.add(interval);
            } else if (interval[1] < left) {
                ansList.add(interval);
            } else {
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }
        //将合并区间之后的结果加入到ansList
        if (!placed) {
            ansList.add(new int[]{left, right});
        }
        int[][] ans = new int[ansList.size()][2];
        for (int i = 0; i < ansList.size(); i++) {
            ans[i] = ansList.get(i);
        }
        return ans;
    }


}
